diff --git a/tools/patman/README b/tools/patman/README
index 7917fc8..02d5829 100644
--- a/tools/patman/README
+++ b/tools/patman/README
@@ -259,12 +259,18 @@
 	unique entries. If omitted, no change log processing is done.
 	Separate each tag with a comma.
 
+Change-Id:
+	This tag is stripped out but is used to generate the Message-Id
+	of the emails that will be sent. When you keep the Change-Id the
+	same you are asserting that this is a slightly different version
+	(but logically the same patch) as other patches that have been
+	sent out with the same Change-Id.
+
 Various other tags are silently removed, like these Chrome OS and
 Gerrit tags:
 
 BUG=...
 TEST=...
-Change-Id:
 Review URL:
 Reviewed-on:
 Commit-xxxx: (except Commit-notes)
diff --git a/tools/patman/commit.py b/tools/patman/commit.py
index 2bf3a0b..48d0529 100644
--- a/tools/patman/commit.py
+++ b/tools/patman/commit.py
@@ -21,6 +21,8 @@
             The dict is indexed by change version (an integer)
         cc_list: List of people to aliases/emails to cc on this commit
         notes: List of lines in the commit (not series) notes
+        change_id: the Change-Id: tag that was stripped from this commit
+            and can be used to generate the Message-Id.
     """
     def __init__(self, hash):
         self.hash = hash
@@ -30,6 +32,7 @@
         self.cc_list = []
         self.signoff_set = set()
         self.notes = []
+        self.change_id = None
 
     def AddChange(self, version, info):
         """Add a new change line to the change list for a version.
diff --git a/tools/patman/patchstream.py b/tools/patman/patchstream.py
index b6455b0..ef06606 100644
--- a/tools/patman/patchstream.py
+++ b/tools/patman/patchstream.py
@@ -2,6 +2,7 @@
 # Copyright (c) 2011 The Chromium OS Authors.
 #
 
+import datetime
 import math
 import os
 import re
@@ -14,7 +15,7 @@
 from series import Series
 
 # Tags that we detect and remove
-re_remove = re.compile('^BUG=|^TEST=|^BRANCH=|^Change-Id:|^Review URL:'
+re_remove = re.compile('^BUG=|^TEST=|^BRANCH=|^Review URL:'
     '|Reviewed-on:|Commit-\w*:')
 
 # Lines which are allowed after a TEST= line
@@ -32,6 +33,9 @@
 # Patch series tag
 re_series_tag = re.compile('^Series-([a-z-]*): *(.*)')
 
+# Change-Id will be used to generate the Message-Id and then be stripped
+re_change_id = re.compile('^Change-Id: *(.*)')
+
 # Commit series tag
 re_commit_tag = re.compile('^Commit-([a-z-]*): *(.*)')
 
@@ -156,6 +160,7 @@
 
         # Handle state transition and skipping blank lines
         series_tag_match = re_series_tag.match(line)
+        change_id_match = re_change_id.match(line)
         commit_tag_match = re_commit_tag.match(line)
         cover_match = re_cover.match(line)
         cover_cc_match = re_cover_cc.match(line)
@@ -177,7 +182,7 @@
             self.state = STATE_MSG_HEADER
 
         # If a tag is detected, or a new commit starts
-        if series_tag_match or commit_tag_match or \
+        if series_tag_match or commit_tag_match or change_id_match or \
            cover_match or cover_cc_match or signoff_match or \
            self.state == STATE_MSG_HEADER:
             # but we are already in a section, this means 'END' is missing
@@ -275,6 +280,16 @@
                 self.AddToSeries(line, name, value)
                 self.skip_blank = True
 
+        # Detect Change-Id tags
+        elif change_id_match:
+            value = change_id_match.group(1)
+            if self.is_log:
+                if self.commit.change_id:
+                    raise ValueError("%s: Two Change-Ids: '%s' vs. '%s'" %
+                        (self.commit.hash, self.commit.change_id, value))
+                self.commit.change_id = value
+            self.skip_blank = True
+
         # Detect Commit-xxx tags
         elif commit_tag_match:
             name = commit_tag_match.group(1)
@@ -345,6 +360,47 @@
             self.warn.append('Found %d lines after TEST=' %
                     self.lines_after_test)
 
+    def WriteMessageId(self, outfd):
+        """Write the Message-Id into the output.
+
+        This is based on the Change-Id in the original patch, the version,
+        and the prefix.
+
+        Args:
+            outfd: Output stream file object
+        """
+        if not self.commit.change_id:
+            return
+
+        # If the count is -1 we're testing, so use a fixed time
+        if self.commit.count == -1:
+            time_now = datetime.datetime(1999, 12, 31, 23, 59, 59)
+        else:
+            time_now = datetime.datetime.now()
+
+        # In theory there is email.utils.make_msgid() which would be nice
+        # to use, but it already produces something way too long and thus
+        # will produce ugly commit lines if someone throws this into
+        # a "Link:" tag in the final commit.  So (sigh) roll our own.
+
+        # Start with the time; presumably we wouldn't send the same series
+        # with the same Change-Id at the exact same second.
+        parts = [time_now.strftime("%Y%m%d%H%M%S")]
+
+        # These seem like they would be nice to include.
+        if 'prefix' in self.series:
+            parts.append(self.series['prefix'])
+        if 'version' in self.series:
+            parts.append("v%s" % self.series['version'])
+
+        parts.append(str(self.commit.count + 1))
+
+        # The Change-Id must be last, right before the @
+        parts.append(self.commit.change_id)
+
+        # Join parts together with "." and write it out.
+        outfd.write('Message-Id: <%s@changeid>\n' % '.'.join(parts))
+
     def ProcessStream(self, infd, outfd):
         """Copy a stream from infd to outfd, filtering out unwanting things.
 
@@ -358,6 +414,9 @@
         fname = None
         last_fname = None
         re_fname = re.compile('diff --git a/(.*) b/.*')
+
+        self.WriteMessageId(outfd)
+
         while True:
             line = infd.readline()
             if not line:
@@ -481,6 +540,7 @@
     for fname in fnames:
         commit = series.commits[count]
         commit.patch = fname
+        commit.count = count
         result = FixPatch(backup_dir, fname, series, commit)
         if result:
             print('%d warnings for %s:' % (len(result), fname))
diff --git a/tools/patman/test.py b/tools/patman/test.py
index e1b94bd..cc61c20 100644
--- a/tools/patman/test.py
+++ b/tools/patman/test.py
@@ -12,6 +12,7 @@
 import gitutil
 import patchstream
 import series
+import commit
 
 
 class TestPatch(unittest.TestCase):
@@ -48,7 +49,8 @@
  arch/arm/cpu/armv7/tegra2/ap20.c           |   57 ++----
  arch/arm/cpu/armv7/tegra2/clock.c          |  163 +++++++++++++++++
 '''
-        expected='''
+        expected='''Message-Id: <19991231235959.0.I80fe1d0c0b7dd10aa58ce5bb1d9290b6664d5413@changeid>
+
 
 From 656c9a8c31fa65859d924cd21da920d6ba537fad Mon Sep 17 00:00:00 2001
 From: Simon Glass <sjg@chromium.org>
@@ -79,7 +81,16 @@
         expfd.write(expected)
         expfd.close()
 
-        patchstream.FixPatch(None, inname, series.Series(), None)
+        # Normally by the time we call FixPatch we've already collected
+        # metadata.  Here, we haven't, but at least fake up something.
+        # Set the "count" to -1 which tells FixPatch to use a bogus/fixed
+        # time for generating the Message-Id.
+        com = commit.Commit('')
+        com.change_id = 'I80fe1d0c0b7dd10aa58ce5bb1d9290b6664d5413'
+        com.count = -1
+
+        patchstream.FixPatch(None, inname, series.Series(), com)
+
         rc = os.system('diff -u %s %s' % (inname, expname))
         self.assertEqual(rc, 0)